// 给定 n 个物品，每个物品有一个重量 wi 和一个价值 vi，同时有一个容量为 C 的背包。
// 目标是选择若干个物品放入背包，使得背包中物品的总重量不超过容量 C，且物品的总价值最大。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int knapsack(int C,int *weights,int *values,int n){
    int **dp = (int**)malloc((n+1) * sizeof(int*));
    for(int i=0;i<=n;i++){
        dp[i] = (int*)malloc((C+1) * sizeof(int));
    }
    
    // dp初始化
    for(int i=0;i<=C;i++){
        dp[0][i] = 0;
    }
    
    for(int i=1;i<=n;i++){
        int w = weights[i-1];
        int v = values[i-1];
        for(int j=0;j<=C;j++){
            if(j>=w){
                dp[i][j] = v + dp[i][j-w] > dp[i-1][j] ? v + dp[i][j-w] : dp[i-1][j];
            }else{
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    return dp[n][C];

}

int main() {
    // 示例输入
    int weights[] = {2, 3, 4, 5}; // 物品的重量
    int values[] = {3, 4, 5, 6};  // 物品的价值
    int C = 5;                    // 背包容量
    int n = sizeof(weights) / sizeof(weights[0]); // 物品数量

    // 调用 knapsack 函数求解最大价值
    int result = knapsack(C, weights, values, n);
    
    // 输出结果
    printf("The maximum value that can be obtained is: %d\n", result);

    return 0;
}